1. Field of the Invention
The present invention relates in general to the field of signal processing, and more specifically to a system and method for pruning output candidate vectors of a look-ahead delta sigma modulator using quantization error based pruning techniques. In one embodiment, pruning techniques use natural and pruned pattern loop filter responses to quantize input signal data.
2. Description of the Related Art
A few signal processing systems implement look-ahead delta-sigma modulators in an attempt to obtain superior input/output signal fidelity by minimizing long term error. “Delta-sigma modulators” are also commonly referred to using other interchangeable terms such as “sigma-delta modulators”, “delta-sigma converters”, “sigma delta converters”, and “noise shapers”.
Conventional research in look-ahead modulators primarily involves two threads. The first are the works of Hiroshi Kato, “Trellis Noise-Shaping Converters and 1-bit Digital Audio,” AES 112th Convention, 2002 May 10–13 Munich, and Hiroshi Kato, Japanese Patent JP, 2003-124812 A, and further refinements described in Harpe, P., Reefman D., Janssen E., “Efficient Trellis-type Sigma Delta Modulator,” AES 114th Convention, 2003 Mar. 22–25 Amsterdam (referred to herein as “Harpe”); James A. S. Angus, “Tree Based Look-ahead Sigma Delta Modulators,” AES 114th Convention, 2003 Mar. 22–25 Amsterdam; James A. S. Angus, “Efficient Algorithms for Look-Ahead Sigma-Delta Modulators,” AES 155th Convention, 2003 Oct. 10–13 New York (referred to herein as “Angus”); Janssen E., Reefman D., “Advances in Trellis based SDM structures,” AES 115th Convention, 2003 Oct. 10–13 New York. This research targets solving the problems of 1-bit encoding of audio data for storage without using the steep anti-alias filters associated with pulse code modulation “PCM.” The advent of super audio compact disc “SACD” audio storage, with its moderate oversampling ratios (32 or 64), motivated this work.
FIG. 1 depicts a prior art signal processing system 100 having a look-ahead delta-sigma modulator 102. The signal source 102 provides an input signal to pre-processing components 104. Preprocessing components 104 include an analog-to-digital converter (“ADC”) and oversampling components to generate a k-bit, digital input signal x(n). For audio applications, x(n) generally represents a signal sampled at 44.1 kHz times an oversampling ratio, such as 64:1. Look-ahead modulator 106 quantizes input signal x(n) and shapes the quantization noise so that most of the quantization noise is moved out of the signal band of interest, e.g. approximately 0–20 kHz for audio applications. Each output signal y(n) (also referred to herein as an “output value”) generally has one of two values selected from the set {+Δ/2, −Δ/2} with “Δ” representing the full swing of y(n). (For convenience, Δ/2 will be represented as +1, and −Δ/2 will be represented as −1.). The output signal y(n) can be further processed and, for example, used to drive an audio sound system or can be recorded directly onto a storage medium.
FIG. 2 depicts a schematic representation of a conventional look-ahead delta-sigma modulator 106 with a look-ahead depth of M. Table 1 describes an embodiment of the symbols used in FIG. 2.
TABLE 1SymbolDefinitionx(n)The nth discrete input signal.XtInput signal vector of length M at atime t. Xt = [x(n), x(n + 1), . . . ,x(n + M − 1)].y(n)The nth discrete output signal.YDiThe ith output delayed by onecandidate vector.CiThe ith cost value vector = H(Di(z)).MLook-ahead depth.NN = rM = The number of output signalcandidate sets under consideration,and r = number of possible valuesfor y(n).ii is selected from the set {0, 1, 2, . . .N − 1}.C(2)iThe ith cost value power.C(2)minThe minimum cost value power attime t.
The look-ahead depth M refers to the dimension of each delayed output candidate vector YDi used to determine output signal y(n). For time t, a negative delayed output candidate vector −YDi, i□ {0,1,2, . . . , N−1}, and the input vector Xt are inputs to noise shaping filter 202(i). For a look-ahead depth of M and y(n)ε{−1, +1}, and without pruning output candidates, each of the N delayed output candidate vectors contains a unique set of elements. Each noise-shaping filter 202(i) of look-ahead delta-sigma modulator 106 uses a common set of filter state variables for time t during the calculations of respective cost value vectors Ci. Filter 202 maintains the actual filter state variables used during the calculation of each y(n). The state variables are updated with the selected y(n) output value. Loop filter 202 processes Xi and −Yi to produce an error value, which in this embodiment is referred to as cost value vector Ci. Cost value vector Ci, and, thus, each element of cost value vector Ci is a frequency weighted error value. In some embodiments of look-ahead delta-sigma modulator 106, input signal vector Xt and delayed output candidate vectors YDi are also used as direct inputs to filter 202(i).
Quantizer error and output generator 203 includes two modules to determine y(n). The cost function minimum search module 204 computes the cost value power, Ci(2), of each cost value vector Ci in accordance with Equation 1, and determines the minimum cost value power at time t.
                              C          i                      (            2            )                          =                              ∑                          t              =              1                                      t              =              M                                ⁢                                          ⁢                                                    [                                  c                  t                                ]                            2                        .                                              Equation        ⁢                                  ⁢        1            “ct” represents a cost value for time t, t=1 through M, in the cost vector Ci. Thus, the cost function minimum search module 204 of quantizer 203 attempts to minimize the energy out of loop filter 202. Minimizing the energy out of loop filter 202 effectively drives the input Ci to a small value, which effectively results in a relatively high loop gain for look-ahead delta-sigma modulator 106 and, thus, modifies the noise shaping transfer function in an undesirable way.
The y(n) selector module 206 selects y(n) as the leading bit of Yi where Ci2min represents the minimum cost value power.
For example, if M=2 and yε{−1,+1}, then N=4, i□{0,1,2,3}, and Table 2 represents each of the Y output candidate vectors and Xt.
TABLE 2Y1Y2Y3Y4Xtyt0011x(n)yt+10101x(n + 1)
If C3(2) represents the minimum cost value power, then selector module 206 selects y(n)=1 because the first bit in output candidate vector Y3 (the output candidate vector associated with C3(2)), equals 1. If C1(2) represents the minimum cost value power, then selector module 206 selects y(n)=0 because the first bit in output candidate vector Y1 (the output candidate vector associated with C1(2)), equals 0.
The second primary thread of look-ahead modulator research involves pulse width modulation (“PWM”) amplifiers based on delta-sigma modulators combined with digital PWM modulation stages. The principal researchers have been Peter Craven and John L. Melanson. In U.S. Pat. No. 5,784,017 entitled “Analogue and Digital Converters Using Pulse Edge Modulations with Non-Linear Correction,” inventor Peter Craven (“Craven”), which is incorporated herein by reference in its entirety, Craven described the use of look-ahead delta-sigma modulators. The purpose of Craven was to ensure stability in alternating edge modulation, an inherently difficult modulation mode to stabilize. In the PWM case, the delta-sigma modulator is operating at a low oversampling ratio (typically 4–16), and quantization noise is a special problem.
FIG. 3 depicts quantizer 106 and noise shaping loop filter 202. The filter 202 can be considered as having a noise transfer function (“NTF”) and a separate signal transfer function (“STF”), as described in commonly assigned U.S. patent application Ser. No. 10/900,877, filed Jul. 28, 2004, entitled “Signal Processing with Lookahead Modulator Noise Quantization Minimization”, inventor John L. Melanson (referred to herein as the “Melanson I Patent”) and in chapter 4 of Norsworthy et al, “Delta Sigma Data Converters—Theory, Design, and Simulation”. 1997, ISBN 0-7803-1045-4. The noise transfer function (“NTF”) equals 1/[1+z−1*H2(z)]. Filter 202 is modeled to indicate the signal transfer function H1(z), the feedback signal transfer function H2(z), and quantization noise 302. The signal transfer function (“STF”) equals H1(z)/[1+z−1*H2(z)]. In some implementations, H1 and H2 are identical. In the general case, H1 and H2 differ.
FIG. 4A depicts a delta sigma modulator 400A with a fourth order noise shaping loop filter 203, quantizer 404, and feedback loop with a unit delay 406, which represents one embodiment of noise shaping filter 202. Constants k0, k1, k2, and k3 are chosen to set poles in the NTF of filter 300. G1 provides a zero (0) in the NTF, which is usually set near a high frequency end of the signal pass band. Filter 300 also includes a double zero at 0 Hz. The STF has a pure pole response cascaded with a pure delay.
FIG. 4B depicts a 3rd order infinite impulse response filter 400B with delays z−1, feedback coefficients C0, C1, and C2, and state variables sv0, sv1, and sv2. In infinite impulse response (“IIR”) filters, one or more state variables are fed back during each time step to modify one or more of the next state variables. This feedback makes it difficult to calculate future values of the filter output for look-ahead applications. The look ahead operation is of special interest in the case of delta-sigma modulation, where the feedback is quantized to a relatively small number of levels, and there are significant advantages to observing more than one potential feedback value at any given time.
One technique to implement an IIR filter adapted for look-ahead operations is depicted in IIR filter process 400C in FIG. 4C, which saves all of the state variables, advances the system clock to find future values, and then restores the state of the state variables. Operation 420 copies state variables to temporary memory, advances states with desired feedback N times (N=2m and m=lookahead depth) in operations 422, calculates state variables using desired output candidate vector elements in operation 424, stores the state variables in operation 426, and advances state one time in operation 428. The 3rd order IIR filter 400B has a look-ahead depth of 4, the current output, and 2 future outputs. Another approach is to have multiple copies of the state variables, each representing the state variable for various states of advance or for various feedback possibilities. These multiple state variables complicate the calculation and increase the size of the state variable memory, in some cases exponentially with the look-ahead depth. In all of these cases, the future values of the input are needed to calculate the future outputs. State variable memory operations 400D for filter 400B and the z^−3 delay at the input is depicted in FIG. 4D.
In a Trellis modulator, output candidate vectors Yi (also referred to as “patterns”), extending for a depth of M sample periods, are tried as candidates for the quantizer output. The power out of the filter, signal Ci, is summed for each output candidate vector Yi, and the lowest power associated output candidate vector is chosen. The first bit of the chosen output candidate vector Yi is chosen as the next output value y(n), and the iteration is repeated for the next input vector Xt+1.
Conventional look-ahead delta sigma modulators require a significant amount of computation and state storage. For a look-ahead depth of 8 bits, in the simplest case 256 copies of the delta sigma modulator are required. Most research has been directed to simplifying the computation by pruning the search so that only a moderate fraction of the 2M cases are calculated. Conventional technology has not proposed a reasonable way to find the closest matching output signal sets for each time t directly given that without pruning there are 2M possible reasonable combinations to search and the length of output signals Y[n] for a 1 minute signal is 60*44100*64 (i.e., 60 seconds, 44.1 kHz sampling frequency, and 64:1 oversampling ratio). Trellis searches and tree searches pruning have all been proposed as solutions to reducing the computation. Angus suggests a pruning technique by organizing look-ahead output candidates into a tree and considering only the branch containing a leaf node with a minimum accumulated error. Some pruning approaches keep the best N searches active at any given time and assume that all future good searches are the children, i.e. descendant branches and nodes, of current good searches. In some cases, this is not the case, and the best candidates for the current will have already been eliminated from contention.